/*
 * Created by SharpDevelop.
 * User: Michael
 * Date: 19/11/2007
 * Time: 8:35 PM
 * 
 * To change this template use Tools | Options | Coding | Edit Standard Headers.
 */

using System;
using System.Collections.Generic;

namespace SudokuSolver
{
	/// <summary>
	/// Description of HiddenSubsets.
	/// </summary>
	public class HiddenSubsets : Technique
	{
		public override bool Run(SudokuGame theGame)
		{
			bool changed = false;
			foreach(Group row in theGame.Rows)
			{
				if(FindHiddenSubsets(row))
					changed = true;
			}
			
			foreach(Group column in theGame.Columns)
			{
				if(FindHiddenSubsets(column))
					changed = true;
			}
			
			foreach(Group block in theGame.Blocks)
			{
				if(FindHiddenSubsets(block))
					changed = true;
			}
			
			return changed;
		}
		
		private bool FindHiddenSubsets(Group thisGroup)
		{
			bool changed = false;
			//get the list of missing numbers for this group
			string missing = "";
			for(int i = 1; i <= 9; i++)
			{
				if(thisGroup.MissingNumber(i))
					missing += i.ToString();
			}
			if(missing.Length != 1)
			{
				//find pairs, triplets and quads
				for(int i = 2; i <= 4; i++)
				{
					List<string> candidateCombos = GenerateCombos(missing, i);
					foreach(string candidateCombo in candidateCombos)
					{
						List<Cell> cellList = GenerateCellList(candidateCombo, thisGroup);
						if(i == cellList.Count)
						{
							//we have found a hidden pair!
							changed = TidyHiddenSubset(thisGroup, cellList, candidateCombo);
						}
					}
				}
			}
			return changed;
		}
		
		private bool TidyHiddenSubset(Group thisGroup, List<Cell> subsetCells, string candidateCombo)
		{
			bool changed = false;
			foreach(Cell candidateCell in subsetCells)
			{
				// eliminate all numbers that aren't in the combo from the cells in the list
				for(int j = 1; j <= 9; j++)
				{
					//if this number isn't in the combo
					if(!candidateCombo.Contains(j.ToString()))
					{
						//remove it from the cell's candidate list
						if(candidateCell.IsPossible(j))
						{
							candidateCell.IsPossible(j, false);
							//something has changed!
							changed = true;
						}
					}
				}
			}
			//eliminate all numbers that are in the combo from cells that aren't
			foreach(Cell cell in thisGroup.Cells)
			{
				if(!subsetCells.Contains(cell))
				{
					foreach(char candidate in candidateCombo)
					{
						int candidateNumber = int.Parse(candidate.ToString());
						if(cell.IsPossible(candidateNumber))
						{
							cell.IsPossible(candidateNumber, false);
							//something changed!
							changed = true;
						}
					}
				}
			}
			return changed;
		}
		
		private List<Cell> GenerateCellList(string candidateCombo, Group group)
		{
			List<Cell> result = new List<Cell>();
			foreach(char candidate in candidateCombo)
			{
				foreach(Cell cell in group.Cells)
				{
					if(cell.IsPossible(int.Parse(candidate.ToString())))
					{
						if(!result.Contains(cell))
							result.Add(cell);
					}
				}
			}
			return result;
		}
		
		private List<string> GenerateCombos(string N, int R)
		{
			List<string> result = new List<string>();
			GenerateCombos(R, N, result, "");
			return result;
		}
		
		private void GenerateCombos(int R, string N, List<string> result, string combo)
		{
			int thisPosition = R - 1;
			if(thisPosition > 0)
			{
				//We may need to recurse
				for(int i = 0; i < N.Length; i++)
				{
					string thisCombo = combo + N[i];
					string childSet = "";
					for(int j = i + 1; j < N.Length; j++)
					{
						childSet = childSet + N[j];
					}
					if(childSet.Length == 0)
					{
						//nothing to pass to the next position, not a possible combo!
						return;
					}
					GenerateCombos(thisPosition, childSet, result, thisCombo);
				}
			} else {
				//this is the last digit, no recursion needed!
				foreach(char thisChar in N)
				{
					result.Add(combo + thisChar);
				}
			}
		}
	}
}
